/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

/*
 * Prototypes
 */
static void
live(efunction_t *function);

static ebool_t
live_check(efunction_t *function, east_list_t *base, east_list_t *tail);

static void
live_check_branch(east_list_t *base, east_node_t *data);

static ebool_t
deep_live_reach_exit_p(elabel_t *label, eint32_t bit);

static ebool_t
live_reach_exit_p(elabel_t *label, eint32_t bit);

static ebool_t
deep_live_reach_load_p(elabel_t *label, eint32_t bit);

static ebool_t
live_reach_load_p(elabel_t *label, eint32_t bit);

static ebool_t
live_store_dead_p(efunction_t *function, elabel_t *label, east_node_t *node);

static ebool_t
live_indirect_load_p(essa_store_t **stores, east_node_t *node, ebool_t global);

/*
 * Initialization
 */
static ebool_t	again;
static ebool_t	first;

/*
 * Implementation
 */
ebool_t
elive(efunction_t *function)
{
    ebool_t	change;

    again = false;
    first = cfg_pass == 0;
    live(function);
    first = false;
    if ((change = again)) {
	do {
	    again = false;
	    live(function);
	} while (again);
    }

    return (change);
}

void
live(efunction_t *function)
{
    east_list_t		*base;
    east_list_t		*list;
    east_node_t		*node;
    east_node_t		*data;
    east_list_t		*prev;
    elabel_t		*label;
    eint32_t		 state;

#define have_none	0
#define have_arg0	1
#define wait_arg1	2
#define have_arg1	4
#define have_jump	8

    base = null;
    data = null;
    cfg_note = null;
    state = have_none;
    prev = function->code;
    label = east_node(prev)->clabel.label;
    for (list = east_next(prev); list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_label:			case eop_block:
		if (state == have_arg0 && live_check(function, base, list))
		    list = base;
		label = node->clabel.label;
		state = have_none;
		break;
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:			case eop_ls:
	    case eop_lvai:
		if (state == wait_arg1)
		    state = have_arg1;
		else {
		    data = node;
		    base = prev;
		    state = have_arg0;
		}
		break;
	    case eop_push:
		if (node->cstack.flags & code_stack_binarg) {
		    if (state != have_arg0)
			base = prev;
		    state = wait_arg1;
		}
		else
		    state = have_none;
		break;
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:
		if (live_store_dead_p(function, label, node)) {
		    essa_del_list_set(function, list);
		    east_next(prev) = east_next(list);
		    list = prev;
		}
		/* implicit value still valid for jump reload optimization */
		state = state == have_arg0 ? have_jump : have_none;
		break;
	    case eop_inc:			case eop_dec:
	    case eop_com:			case eop_inv:
	    case eop_neg:			case eop_signbit:
	    case eop_signum:			case eop_rational:
	    case eop_integer_p:			case eop_rational_p:
	    case eop_float_p:			case eop_real_p:
	    case eop_complex_p:			case eop_number_p:
	    case eop_finite_p:			case eop_inf_p:
	    case eop_nan_p:			case eop_num:
	    case eop_den:			case eop_real:
	    case eop_imag:			case eop_arg:
	    case eop_conj:			case eop_floor:
	    case eop_trunc:			case eop_round:
	    case eop_ceil:			case eop_abs:
	    case eop_sqrt:			case eop_cbrt:
	    case eop_sin:			case eop_cos:
	    case eop_tan:			case eop_asin:
	    case eop_acos:			case eop_atan:
	    case eop_sinh:			case eop_cosh:
	    case eop_tanh:			case eop_asinh:
	    case eop_acosh:			case eop_atanh:
	    case eop_proj:			case eop_exp:
	    case eop_log:			case eop_log2:
	    case eop_log10:
		if (state == have_arg0 &&
		    live_check(function, base, east_next(list)))
		    list = base;
		state = have_none;
		break;
	    case eop_ne:			case eop_lt:
	    case eop_le:			case eop_eq:
	    case eop_ge:			case eop_gt:
	    case eop_and:			case eop_or:
	    case eop_xor:			case eop_mul2:
	    case eop_div2:			case eop_shl:
	    case eop_shr:			case eop_add:
	    case eop_sub:			case eop_mul:
	    case eop_div:			case eop_trunc2:
	    case eop_rem:			case eop_atan2:
	    case eop_pow:			case eop_hypot:
	    case eop_complex:
		if (state == have_arg1 &&
		    live_check(function, base, east_next(list)))
		    list = base;
		state = have_none;
		break;
	    case eop_note:
		cfg_note = node;
		break;
	    case eop_jt:			case eop_jf:
		if (state == have_arg0 || state == have_jump) {
		    /* next code must be eop_label or eop_entry */
		    label = node->clabel.label;
		    if (label->srcs->offset == 1)
			live_check_branch(elabel_list(label), data);
		    prev = list;
		    list = east_next(list);
		    if (list && east_node(list)->code == eop_block)
			live_check_branch(list, data);
		    list = prev;
		}
		state = have_none;
		break;
	    case eop_j:
		if (state == have_arg0 || state == have_jump) {
		    /* next code must be eop_label or eop_entry */
		    label = node->clabel.label;
		    if (label->srcs->offset == 1)
			live_check_branch(elabel_list(label), data);
		}
		state = have_none;
		break;
	    default:
		if (state == have_arg0 && live_check(function, base, list))
		    list = base;
		state = have_none;
		break;
	}
    }
}

static ebool_t
live_check(efunction_t *function, east_list_t *base, east_list_t *tail)
{
    east_list_t		*list;
    east_node_t		*node;

    if (ecfg_implicit_used_p(tail))
	return (false);

    for (list = east_next(base); list != tail; list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		essa_del_list_use(function, list);
		break;
	    default:
		break;
	}
    }

    east_next(base) = tail;

#if 0
    /* FIXME must mask out redundant automatically generated code:
     *	o push/pop on initializers
     *	o duplicated loop test
     */
    if (first)
	/* warn about unused computation */
	ecfg_warn(parse, "code has no effect");
#endif

    return (again = true);
}

static void
live_check_branch(east_list_t *base, east_node_t *data)
{
    east_list_t		*list;
    east_node_t		*node;

    for (list = east_next(base); list; base = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:			case eop_ls:
	    case eop_lvai:
		if (node == data) {
		    east_next(base) = east_next(list);
		    again = true;
		}
	    default:
		return;
	    case eop_note:
		cfg_note = node;
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:			case eop_ss:
	    case eop_sst:			case eop_ssv:
	    case eop_svai:			case eop_push:
	    case eop_pusht:			case eop_pushv:
		break;
	}
    }
}

#define zmsk			thr_zr
static ebool_t
deep_live_reach_exit_p(elabel_t *label, eint32_t bit)
{
    elabel_t		**dsts;
    eint32_t		  index;

    if (label->dsts->offset == 0)
	/* value reached function exit */
	return (true);

    if (mpz_tstbit(zmsk, label->ident))
	/* basic block already visited */
	return (false);
    mpz_setbit(zmsk, label->ident);

    if (mpz_tstbit(label->set, bit))
	/* value is overwritten in this basic block */
	return (false);

    dsts = label->dsts->v.obj;
    for (index = 0; index < label->dsts->offset; index++)
	if (deep_live_reach_exit_p(dsts[index], bit))
	    /* any of the possible destinations reaches function exit */
	    return (true);

    /* value did not reach function exit */
    return (false);
}

static ebool_t
live_reach_exit_p(elabel_t *label, eint32_t bit)
{
    elabel_t		**dsts;
    eint32_t		  index;

    if (label->dsts->offset == 0)
	/* value reached function exit */
	return (true);

    /* remember toplevel basic block already visited */
    mpz_setbit(zmsk, label->ident);

    dsts = label->dsts->v.obj;
    for (index = 0; index < label->dsts->offset; index++)
	if (deep_live_reach_exit_p(dsts[index], bit))
	    /* any of the possible destinations reaches function exit */
	    return (true);

    /* value did not reach function exit */
    return (false);
}

static ebool_t
deep_live_reach_load_p(elabel_t *label, eint32_t bit)
{
    elabel_t		**dsts;
    eint32_t		  index;

    if (mpz_tstbit(zmsk, label->ident))
	/* basic block already visited */
	return (false);
    mpz_setbit(zmsk, label->ident);

    if (mpz_tstbit(label->use, bit))
	/* if value is actually used */
	return (true);

    if (mpz_tstbit(label->set, bit))
	/* value overwritten in this basic block */
	return (false);

    dsts = label->dsts->v.obj;
    for (index = 0; index < label->dsts->offset; index++)
	if (deep_live_reach_load_p(dsts[index], bit))
	    /* any of the possible destinations load value */
	    return (true);

    /* value not loaded */
    return (false);
}

static ebool_t
live_reach_load_p(elabel_t *label, eint32_t bit)
{
    elabel_t		**dsts;
    eint32_t		  index;

    if (label->dsts->offset == 0)
	/* value reached function exit */
	return (false);

    /* remember toplevel basic block already visited */
    mpz_set_ui(zmsk, 0);
    mpz_setbit(zmsk, label->ident);

    dsts = label->dsts->v.obj;
    for (index = 0; index < label->dsts->offset; index++)
	if (deep_live_reach_load_p(dsts[index], bit))
	    /* any of the possible destinations load value */
	    return (true);

    /* value not loaded */
    return (false);
}

static ebool_t
live_store_dead_p(efunction_t *function, elabel_t *label, east_node_t *node)
{
    eint32_t		  bit;
    eint32_t		  ssa;
    esymbol_t		 *atom;
    essa_load_t		 *load;
    essa_load_t		**loads;
    essa_store_t	**stores;
    ebool_t		  global;

    atom = node->csymbol.symbol;

    if (node->code == eop_sb &&
	/* exception object is "volatile" */
	atom->offset == function->tryoff)
	return (false);

    /* symbol offset in bit vectors */
    bit = node->csymbol.bit;

    /* FIXME access may only happen through a pointer or record field,
     * what is just masked out for now */
    if (mpz_tstbit(function->ptr, bit) || mpz_tstbit(function->esc, bit))
	return (false);

    /* ssa counter of the store */
    ssa = node->csymbol.ssa;

    /* fast check for common case */
    loads = function->loads->v.obj;
    if ((load = loads[bit])) {
	if (load->data[ssa].node)
	    /* direct load */
	    return (false);
	if (ssa < load->top && load->data[ssa + 1].node)
	    /* load after phi increment */
	    return (false);

	if (label->loop && load->data[ssa].node == null &&
	    ssa > load->bot && load->data[ssa - 1].node)
	    /* value match conditions for a loop counter because:
	     *	o label is in a loop
	     *	o there is no load of the associated store
	     *	o there is a load of the previous counter
	     * this matches the intermediate representation for:
	     *	for (i = 0; i < n; i++)
	     *	    something;
	     * that is somewhat like:
	     *		int 0
	     *		st i#1
	     *	L1: 1
	     *		something
	     *		ld i#2		<- phi bit increment due to loop
	     *		inc
	     *		st i#3		<- store being tested
	     *		push
	     *		ld n#1
	     *		lt
	     *       jt L1		<- use of 'i' after jump should be i#4
	     */
	    return (false);
    }

    /* follow code paths checking for a load */
    if (live_reach_load_p(label, bit))
	return (false);

    stores = function->stores->v.obj;
    global = atom->a_global || atom->a_field;
    if (live_indirect_load_p(stores, node, global))
	return (false);

    if (global) {
	mpz_set_ui(zmsk, 0);
	if (live_reach_exit_p(label, bit))
	    /* possibly last store in function body */
	    return (false);
    }

    /* zombie alert! */
    return (again = true);
}
#undef zmsk

static ebool_t
live_indirect_load_p(essa_store_t **stores, east_node_t *node, ebool_t global)
{
    eint32_t		 ssa;
    essa_store_t	*store;

    /* if there is a gap in the store/load counters, the counter was
     * incremented due to a function call (if global), pointer store
     * or phi bit set (what implies a load, but not confirmed here).
     */

    ssa = node->csymbol.ssa + 1;
    store = stores[node->csymbol.bit];

    return (/* last store */
	    (global && ssa > store->top) ||
	    /* empty entry means there was an indirect load */
	    (ssa < store->top && store->data[ssa].list == null));
}
